//
//  QuickSort.c
//  AlgorithmLearning
//
//  Created by aron on 2017/11/2.
//  Copyright © 2017年 aron. All rights reserved.
//

#include "QuickSort.h"
#include "InsertionSort.h"

void swap(ElementType* a, ElementType* b) {
    ElementType tmp = *a;
    *a = *b;
    *b = tmp;
}

// 获取钮元
ElementType Median3(ElementType arr[], int left, int right) {
    ElementType center = (left + right) / 2;
    if (arr[left] > arr[center]) {
        swap(&arr[left], &arr[center]);
    }
    if (arr[left] > arr[right]) {
        swap(&arr[left], &arr[right]);
    }// Left<-min
    if (arr[center] > arr[right]) {
        swap(&arr[center], &arr[right]);
    }// Right<-max
    // Left < Center < Rightr
    // 最大的值是固定在最右边的
    // 钮元放在 right-1 位置
    swap(&arr[center], &arr[right - 1]);
    return arr[right - 1];
}

#define CutOff  (3)

void QSortCore(ElementType arr[], int left, int right) {
    if (left >= right) {
        // 一个元素的情况
        return;
    }
    if (right - left < CutOff) {
        // 使用插入排序
        Insertionsort(arr + left, right - left + 1);
    } else {
        ElementType pivot = Median3(arr, left, right);
        
        int rightPointer = right - 1; // 因为arr[--rightPointer]所以从right-2位置开始
        int leftPointer = left;
        
        while (leftPointer < rightPointer) {
            
            while (arr[--rightPointer] > pivot) { }
            
            while (arr[++leftPointer] < pivot) { }
            
            if (leftPointer < rightPointer) {
                swap(&arr[rightPointer], &arr[leftPointer]);
            }
        }
        // 复位钮元，需要使用leftPointer,
        // leftPointer指向的值确保都是大于等于钮元的值
        // rightPointer会出现小于钮元的值，复位钮元会出问题
        swap(&arr[leftPointer], &arr[right - 1]);
        
        // 左边递归
        QSortCore(arr, left, leftPointer - 1);
        
        // 右边递归
        QSortCore(arr, leftPointer + 1, right);
    }
}

void Quicksort(ElementType arr[], int count) {
    QSortCore(arr, 0, count-1);
}

